Transforms, which take data from one domain (e.g., sampled data) to another (e.g., frequency space), are used in many signal and/or image processing applications. Such transforms are used for a variety of applications, including, but not limited to data analysis, feature identification and/or extraction, signal correlation, data compression, or data embedding. Many of these transforms require efficient implementation for real time and/or fast execution whether or not compression is used as part of the data processing.
Data compression is desirable in many data handling processes, where too much data is present for practical applications using the data. Commonly, compression is used in communication links, to reduce transmission time or required bandwidth. Similarly, compression is preferred in image storage systems, including digital printers and copiers, where “pages” of a document to be printed may be stored temporarily in memory. Here the amount of media space on which the image data is stored can be substantially reduced with compression. Generally speaking, scanned images, i.e., electronic representations of hard copy documents, are often large, and thus make desirable candidates for compression.
In data processing, data is typically represented as a sampled discrete function. The discrete representation is either made deterministically or statistically. In a deterministic representation, the point properties of the data are considered, whereas, in a statistical representation, the average properties of the data are specified. In particular examples referred to herein, the terms images and image processing will be used. However, those skilled in the art will recognize that the present invention is not meant to be limited to processing still images but is applicable to processing different data, such as audio data, scientific data, video data, sensor data, etc.
In a digital image processing system, digital image signals are formed by first dividing a two-dimensional image into a grid. Each picture element, or pixel, in the grid has associated therewith a number of visual characteristics, such as brightness and color. These characteristics are converted into numeric form. The digital image signal is then formed by assembling the numbers associated with each pixel in the image into a sequence which can be interpreted by a receiver of the digital image signal.
Signal and image processing frequently require converting input data into transform coefficients for the purposes of analysis. Often only a quantized version of the transform coefficients is needed, such as, for example, JPEG/MPEG data compression or audio/voice compression. Many such applications need to be done fast in real time such as the generation of JPEG data for high speed printers.
One compression technology defined in the JPEG standard, as well as other emerging compression standards, is discrete cosine transform (DCT) coding, wherein an input image is divided into many uniform image blocks with data samples in each, typically in an 8×8 array of data samples, to achieve image compression. Images compressed using DCT coding are decompressed using an inverse transform known as the inverse DCT (IDCT). A two-dimensional forward discrete cosine transform (FDCT) function is applied to each block to transform the data samples into a set of transform coefficients to remove the spatial redundancy.
In general, the forward transform will produce real-valued data, not necessarily integers. To achieve data compression, the transform coefficients are converted to integers by the process of quantization. The resulting integers are then passed on for possible further encoding or compression before being stored or transmitted.
The two basic components of an image compression/decompression system are the encoder and the decoder. The encoder compresses the “source” image (the original digital image) and provides an output of compressed data (or coded data). The compressed data may be either stored or transmitted, but at some point are fed to the decoder. The decoder recreates or “reconstructs” an image from the compressed data.
In general, a data compression encoding system may include three basic parts: an encoder model, an encoder statistical model, and an entropy encoder. The encoder model generates a sequence of “descriptors” that is an abstract representation of the image. The statistical model converts these descriptors into symbols and passes them on to the entropy encoder. The entropy encoder, in turn, compresses the symbols to form the compressed data. The encoder may require external tables. That is, tables specified externally when the encoder is invoked. Generally, there are two classes of tables; model tables that are needed in the procedures that generate the descriptors, and entropy-coding tables that are needed by the JPEG entropy-coding procedures.
JPEG uses two techniques for entropy encoding: Huffman coding and arithmetic coding. Similarly to the encoder, the decoder may include basic parts that have an inverse function relative to the parts of the encoder.
JPEG compressed data contains two classes of segments: entropy-coded segments and marker segments. Other parameters that are needed by many applications are not part of the JPEG compressed data format. Such parameters may be needed as application-specific “wrappers” surrounding the JPEG data; e.g., image aspect-ratio, pixel shape, orientation of image, etc.
Within the JPEG compressed data, the entropy-coded segments contain the entropy-coded data, whereas the marker segments contain header information, tables, and other information required to interpret and decode the compressed image data. Marker segments always begin with a “marker”, a unique 2-byte code that identifies the functions of the segment.
To perform a display (or print or audio) operation, it may be necessary for the display device to scale an image to a larger or smaller size. The scaling of the images may be performed as a linear operation. The array of coefficients describing the intensity of the colors of the pixels of the image is transformed to an array of coefficients of the scaled image by a matrix operation.
This transformation may be performed in any representation of the image, but may depend on such a representation. As long as the representation is linear with respect to the pixel values the transformation stays linear.
The scale factor is a number which expresses the ratio of the number of samples in the image before and after the scaling. Usually the scaling is performed block-wise, where the size of the block (which may be the entire signal) is determined by the scale factor, the demanded efficiency of the operation and the quality of the resulting signal. Choosing larger blocks may yield better quality but lesser efficiency, because the larger blocks allows the scaling factor to be approximated more accurately. The scale factors with small integers as denominators and numerators allow smaller blocks, larger integers may force larger blocks.
The emphasis of the present invention is addressing high-end color printer performance for scaling operations. Currently, scaling a continuous tone JPEG image has a strong undesirable effect on the throughput of the printer. Conventional prior art image reduction processes typically involve doing an IDCT transform on each 8×8 DCT block to create real domain data (64 samples), reducing the image in the pixel domain, and then doing a FDCT to return to the DCT domain. The main problem with this approach is that it is computationally expensive. For full-page images the IDCT and FDCT calculations alone could exceed the total processing time available, particularly if the images are being reduced down to make them fit on a page.
In one reference incorporated above, “Reduction of N DCT blocks into One Block” by Trenary et al., a solution has been developed wherein one-dimensional DCT domain reduction methods merge N blocks along one dimension into one block, resulting in a significant transactional savings. This approach offers computationally efficient advantages in 1/n “downscaling” operations. However, where the same method and system is utilized in “up-scaling” operations, extra computational cycles are required, reducing efficiency advantages. Moreover, the extra computational cycles introduce additional opportunities for the occurrence of errors through additional “round-off” steps.
One area where both data transform and scaling operations are required is high impression-per-minute (“ipm”) printing during “contone” (continuous tone; e.g., photographic) image scaling. The criticality of the problem increases as the printer speed is increased. What is needed is a computationally efficient system and method to provide transform and scaling operations in data processing, and more particularly in data transform operations that use scaled terms. More particularly, an improved system and method is required to address high-end color printer performance for scaling operations.